/*
** $Id: lgc.c $
** Garbage Collector(GC,垃圾回收)
** See Copyright Notice in lua.h
*/

#define lgc_c
#define LUA_CORE

#include "lprefix.h"

#include <stdio.h>
#include <string.h>


#include "lua.h"

#include "ldebug.h"
#include "ldo.h"
#include "lfunc.h"
#include "lgc.h"
#include "lmem.h"
#include "lobject.h"
#include "lstate.h"
#include "lstring.h"
#include "ltable.h"
#include "ltm.h"


/*
** 每次清除过程中最多清除的元素数量
** (一方面，它要足够大，以消散固定的开销；另一方面，它又要足够小，使得垃圾收集器可以进行小步骤的清理。这样可以使得垃圾收集过程更加平滑，避免对系统产生过大的压力)
*/
#define GCSWEEPMAX	100

/*
** 在每个单独步骤中调用的最大终结器数量
*/
#define GCFINMAX	10


/*
** 调用一个终结器的消耗
*/
#define GCFINALIZECOST	50


/*
** 相当于一个单位的“工作”(访问一个槽，清除一个对象等)，以字节为单位
*/
#define WORK2MEM	sizeof(TValue)


/*
** 用于调整’pause': 'pause'的实际用法类似于'pause / PAUSEADJ' (值是经过测试而选用的)
*/
#define PAUSEADJ		100


/* 所有颜色位的掩码 */
#define maskcolors	(bitmask(BLACKBIT) | WHITEBITS)

/* 所有GC位的掩码 */
#define maskgcbits      (maskcolors | AGEBITS)


/* 抹去所有颜色位然后设置成当前白色位 */
#define makewhite(g,x)	\
  (x->marked = cast_byte((x->marked & ~maskcolors) | luaC_white(g)))

/* 将一个对象置为灰色 (不是白色也不是黑色) */
#define set2gray(x)	resetbits(x->marked, maskcolors)


/* 将一个对象设置成黑色(来自任何颜色) */
#define set2black(x)  \
  (x->marked = cast_byte((x->marked & ~WHITEBITS) | bitmask(BLACKBIT)))


#define valiswhite(x)   (iscollectable(x) && iswhite(gcvalue(x)))

#define keyiswhite(n)   (keyiscollectable(n) && iswhite(gckey(n)))


/*
** 对值中的对象进行受保护访问
*/
#define gcvalueN(o)     (iscollectable(o) ? gcvalue(o) : NULL)

#define markvalue(g,o) { checkliveness(g->mainthread,o); \
  if (valiswhite(o)) reallymarkobject(g,gcvalue(o)); }

#define markkey(g, n)	{ if keyiswhite(n) reallymarkobject(g,gckey(n)); }

#define markobject(g,t)	{ if (iswhite(t)) reallymarkobject(g, obj2gco(t)); }

/*
** 标记一个能为NULL的对象 (要么是因为它确实是可选的，要么是因为它被剥离为调试信息，要么是因为它在一个未完成的结构中)
*/
#define markobjectN(g,t)	{ if (t) markobject(g,t); }

static void reallymarkobject (global_State *g, GCObject *o);
static lu_mem atomic (lua_State *L);
static void entersweep (lua_State *L);


/*
** {======================================================
** 通用方法
** =======================================================
*/


/*
** hash数组中最后一个元素
*/
#define gnodelast(h)	gnode(h, cast_sizet(sizenode(h)))


static GCObject **getgclist (GCObject *o) {
  switch (o->tt) {
    case LUA_VTABLE: return &gco2t(o)->gclist;
    case LUA_VLCL: return &gco2lcl(o)->gclist;
    case LUA_VCCL: return &gco2ccl(o)->gclist;
    case LUA_VTHREAD: return &gco2th(o)->gclist;
    case LUA_VPROTO: return &gco2p(o)->gclist;
    case LUA_VUSERDATA: {
      Udata *u = gco2u(o);
      lua_assert(u->nuvalue > 0);
      return &u->gclist;
    }
    default: lua_assert(0); return 0;
  }
}


/*
** 通过已知类型将一个可收集对象’o'连接至‘p’列表
*/
#define linkgclist(o,p)	linkgclist_(obj2gco(o), &(o)->gclist, &(p))

static void linkgclist_ (GCObject *o, GCObject **pnext, GCObject **list) {
  lua_assert(!isgray(o));  /* 不能够在灰色列表中 */
  *pnext = *list;
  *list = o;
  set2gray(o);
}


/*
** 连接一个通用可收集对象’o'至‘p'列表
*/
#define linkobjgclist(o,p) linkgclist_(obj2gco(o), getgclist(o), &(p))



/*
** 清除table中空节点的key。如果节点是空的，标记他的节点为dead
** 这允许key的收集，但是保持在table中的节点：他的移除会破坏(break)链并破坏表遍历
** 其他地方永远不会操作死亡key，因为他关联的值足以表示这个条目在逻辑上是空的
*/
static void clearkey (Node *n) {
  lua_assert(isempty(gval(n)));
  if (keyiscollectable(n))
    setdeadkey(n);  /* 无用的key; 移除他 */
}


/*
** 一个key/value能否从一个弱表中被清理,不能被收集的对象不会被从弱表中移除
** 字符串表现为“值”，所以也不会被移除
** 对于其他对象：如果确实被收集了，不能保留他们，对于正在终结的被终结对象，key中保留他们，但不在值中保留
*/
static int iscleared (global_State *g, const GCObject *o) {
  if (o == NULL) return 0;  /* 不可收集值 */
  else if (novariant(o->tt) == LUA_TSTRING) {
    markobject(g, o);  /* 字符串是‘值’，不会是弱的 */
    return 0;
  }
  else return iswhite(o);
}


/*
** 将收集器向前移动的屏障，即标记白色对象‘v'被黑色对象’o'指向
** 在分代模式中，如果’o'是老的，那么‘v'也一定变老。然而，他不能被直接修改成OLD(老)的，因为他可能仍然指向non-old(非老)的对象，因此，他被标记为OLD0,
** 在下一个周期将被变成OLD1，并且在下一个周期将被最终变成OLD(常规OLD)，到那时他所指向的任何对象都是OLD
** 如果在增量清除阶段被调用，他清除黑色物体为白色(清除)以避免同一对象的其他屏障调用(这不能再分代模式中执行，因为他的清除并不区分白色对象和已死亡对象)
*/
void luaC_barrier_ (lua_State *L, GCObject *o, GCObject *v) {
  global_State *g = G(L);
  lua_assert(isblack(o) && iswhite(v) && !isdead(g, v) && !isdead(g, o));
  if (keepinvariant(g)) {  /* 必须保持不变式? */
    reallymarkobject(g, v);  /* 恢复不变式 */
    if (isold(o)) {
      lua_assert(!isold(v));  /* 白色对象不能变老 */
      setage(v, G_OLD0);  /* 恢复分代的不变式 */
    }
  }
  else {  /* 清除阶段 */
    lua_assert(issweepphase(g));
    if (g->gckind == KGC_INC)
      makewhite(g, o);  /* 标记’o'为白色以避免其他屏障 */
  }
}


/*
** 将收集器向后移动的屏障(将指向白色物体的黑色物体再次标记为灰色)
*/
void luaC_barrierback_ (lua_State *L, GCObject *o) {
  global_State *g = G(L);
  lua_assert(isblack(o) && !isdead(g, o));
  lua_assert((g->gckind == KGC_GEN) == (isold(o) && getage(o) != G_TOUCHED1));
  if (getage(o) == G_TOUCHED2)  /* 已经在灰色列表中? */
    set2gray(o);  /* 再次标记为灰色 */
  else  /* 将其链接到‘grayagain’ */
    linkobjgclist(o, g->grayagain);
  if (isold(o))  /* 分代模式? */
    setage(o, G_TOUCHED1);  /* 当前周期touched */
}


// 让对象永远不被GC收集
void luaC_fix (lua_State *L, GCObject *o) {
  global_State *g = G(L);
  lua_assert(g->allgc == o);  /* 对象必须是‘allgc'列表的第一个(创建完立马要来设置)! */
  set2gray(o);  /* 将永远是gray */
  setage(o, G_OLD);  /* 永远是old */
  g->allgc = o->next;  /* 从‘allgc'列表中移除对象 */
  o->next = g->fixedgc;  /* 链接'fixedgc'列表 */
  g->fixedgc = o;
}


/*
** 创建一个新的可收集对象(通过传入的type, size, offset)并且将他和‘allgc'列表链接
*/
GCObject *luaC_newobjdt (lua_State *L, int tt, size_t sz, size_t offset) {
  global_State *g = G(L);
  char *p = cast_charp(luaM_newobject(L, novariant(tt), sz));
  GCObject *o = cast(GCObject *, p + offset);
  o->marked = luaC_white(g);
  o->tt = tt;
  o->next = g->allgc;
  g->allgc = o;
  return o;
}


GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
  return luaC_newobjdt(L, tt, sz, 0);
}

/* }====================================================== */



/*
** {======================================================
** 标记方法
** =======================================================
*/


/*
** 标记一个对象. 没有uservalue的Userdata,string和关闭的upvalue被访问并且转为黑色
** 打开的upvalue已经通过‘twups'列表中各自的线程中的被间接地连接，因此他们不会放入灰色列表中
** 然而，他们保持灰色以避免屏障，因为他们的值将被线程或'remarkupvals'重新访问
** 之后其他对象被添加到灰色列表中被访问(并且转为灰色)
** userdata和upvalue都能递归调用这个函数，但是这种递归只能在两个级别上执行：一个upvalue不能引用另一个upvalue(只能闭包可以)，并且userdata的元表必须是一个table
*/
static void reallymarkobject (global_State *g, GCObject *o) {
  switch (o->tt) {
    case LUA_VSHRSTR:
    case LUA_VLNGSTR: {
      set2black(o);  /* 没有东西可访问 */
      break;
    }
    case LUA_VUPVAL: {
      UpVal *uv = gco2upv(o);
      if (upisopen(uv))
        set2gray(uv);  /* 打开的upvalue保持灰色 */
      else
        set2black(uv);  /* 关闭的upvalue在这里被访问 */
      markvalue(g, uv->v.p);  /* 标记他们的内容 */
      break;
    }
    case LUA_VUSERDATA: {
      Udata *u = gco2u(o);
      if (u->nuvalue == 0) {
        markobjectN(g, u->metatable);  /* 标记他的元表 */
        set2black(u);  /* 没有其他东西标记 */
        break;
      }
      /* else... */
    }  /* FALLTHROUGH */
    case LUA_VLCL: case LUA_VCCL: case LUA_VTABLE:
    case LUA_VTHREAD: case LUA_VPROTO: {
      linkobjgclist(o, g->gray);  /* 之后被访问 */
      break;
    }
    default: lua_assert(0); break;
  }
}


/*
** 标记基础类型的元方法
*/
static void markmt (global_State *g) {
  int i;
  for (i=0; i < LUA_NUMTAGS; i++)
    markobjectN(g, g->mt[i]);
}


/*
** 标记being-finalized列表中的所有对象
*/
static lu_mem markbeingfnz (global_State *g) {
  GCObject *o;
  lu_mem count = 0;
  for (o = g->tobefnz; o != NULL; o = o->next) {
    count++;
    markobject(g, o);
  }
  return count;
}


/*
** 对一个没有被标记的线程，模拟每个打开的upvalue和他的值之间的屏障
** (如果线程已经被收集，值将被赋值给upvalue，但是对于屏障来说可能为时已晚
** 屏障不需要检测颜色：一个没有被标记的线程必须是年轻的；upvalue不能比他们的线程老；因此所有任何被访问的upvalue也必须是年轻的)
** 也从列表中移除线程，因为他已经被访问过了。同时移除没有upvalue的线程，因为他们没有什么需要被检查的。如果线程在之后获得了一个upvalue，他将被再次链接到列表中
*/
static int remarkupvals (global_State *g) {
  lua_State *thread;
  lua_State **p = &g->twups;
  int work = 0;  /* 预估了这个函数做了多少工作 */
  while ((thread = *p) != NULL) {
    work++;
    if (!iswhite(thread) && thread->openupval != NULL)
      p = &thread->twups;  /* 保留标记的线程，并保留标记的upvalue */
    else {  /* 线程没有被标记或者没有upvalue */
      UpVal *uv;
      lua_assert(!isold(thread) || thread->openupval == NULL);
      *p = thread->twups;  /* 将线程从列表中移除 */
      thread->twups = thread;  /* 标记他不在列表中 */
      for (uv = thread->openupval; uv != NULL; uv = uv->u.open.next) {
        lua_assert(getage(uv) <= getage(thread));
        work++;
        if (!iswhite(uv)) {  /* upvalue已经被访问? */
          lua_assert(upisopen(uv) && isgray(uv));
          markvalue(g, uv->v.p);  /* 标记他的值 */
        }
      }
    }
  }
  return work;
}


static void cleargraylists (global_State *g) {
  g->gray = g->grayagain = NULL;
  g->weak = g->allweak = g->ephemeron = NULL;
}


/*
** 标记root集并且重置所有灰色列表，开始新的收集
*/
static void restartcollection (global_State *g) {
  cleargraylists(g);
  markobject(g, g->mainthread);
  markvalue(g, &g->l_registry);
  markmt(g);
  markbeingfnz(g);  /* 标记上一个周期留下的所有终结对象 */
}

/* }====================================================== */


/*
** {======================================================
** 遍历函数
** =======================================================
*/


/*
** 检测对象‘o'是否应该保留在’grayagain‘列表中，由’correctgraylist'进行后续处理
** (他会把所有列表中的老对象放入，并将所有的工作留给‘correctgraylist’，但避免添加将被删除的元素会更有效)
** 只有TOUCHED1对象需要再列表中，TOUCHED2不需要放回gray列表，但他必须变成OLD
** (这就是'correctgraylist'找到TOUCHED2对象时所做的)
*/
static void genlink (global_State *g, GCObject *o) {
  lua_assert(isblack(o));
  if (getage(o) == G_TOUCHED1) {  /* 这个周期被touched? */
    linkobjgclist(o, g->grayagain);  /* 链接回'grayagain' */
  }  /* 其他的都不要连接回去 */
  else if (getage(o) == G_TOUCHED2)
    changeage(o, G_TOUCHED2, G_OLD);  /* OLD */
}


/*
** 遍历具有弱值的表并将其链接到适当的列表. 在广播阶段，将他保留在‘grayagain‘列表，以便在atomic阶段访问.
** 在atomic阶段，如果表有任何白色value，将其放入’weak'列表，以便清理
*/
static void traverseweakvalue (global_State *g, Table *h) {
  Node *n, *limit = gnodelast(h);
  /* 如果有数组部分，假定他有白色值(现在不遍历他，只是检测) */
  int hasclears = (h->alimit > 0);
  for (n = gnode(h, 0); n < limit; n++) {  /* 遍历hash部分 */
    if (isempty(gval(n)))
      clearkey(n);
    else {
      lua_assert(!keyisnil(n));
      markkey(g, n);  /* 标记key */
      if (!hasclears && iscleared(g, gcvalueN(gval(n))))  /* value是白色? */
        hasclears = 1;  /* table要被清理 */
    }
  }
  if (g->gcstate == GCSatomic && hasclears)
    linkgclist(h, g->weak);  /* 必须在之后清除 */
  else
    linkgclist(h, g->grayagain);  /* 必须在atomic阶段重新遍历 */
}


/*
** 遍历一个蜉蝣(弱key)表，并且将其链接到对应的列表，如果有对象在这个遍历中被标记返回true (意味着收集必须继续).
** 在传播阶段，将表保留在‘grayagain'列表中，以便在atomic阶段再次访问
** 在atomic阶段，如果 表有任何白色->白色条目，他必须在短暂收集期间重新访问(因为该key可能变成黑色)
** 否则，如果他有任何白色key，表必须被清理(atomic阶段)。
** 在分代模式中，一些表必须保留在灰色列表中，以便后面处理；这是有’genlink'完成的
*/
static int traverseephemeron (global_State *g, Table *h, int inv) {
  int marked = 0;  /* 如果对象在这次遍历中被标记为true */
  int hasclears = 0;  /* 如果表有白色key为true */
  int hasww = 0;  /* 如果表有条目 "white-key -> white-value"为true */
  unsigned int i;
  unsigned int asize = luaH_realasize(h);
  unsigned int nsize = sizenode(h);
  /* 遍历数组部分 */
  for (i = 0; i < asize; i++) {
    if (valiswhite(&h->array[i])) {
      marked = 1;
      reallymarkobject(g, gcvalue(&h->array[i]));
    }
  }
  /* 遍历hash部分; 如果'inv', 遍历下行(see 'convergeephemerons') */
  for (i = 0; i < nsize; i++) {
    Node *n = inv ? gnode(h, nsize - 1 - i) : gnode(h, i);
    if (isempty(gval(n))) /* 如果value是空的，那么key-value都应该被清除 */
      clearkey(n);
    else if (iscleared(g, gckeyN(n))) {  /* key还没有被标记? */
      hasclears = 1;  /* 表必须被清理 */
      if (valiswhite(gval(n)))  /* 值还没有被标记? */
        hasww = 1;  /* key和value都是白色的条目 */
    }
    else if (valiswhite(gval(n))) {  /* 值还没有被标记?(这里表示key已经被标记，强引用) */
      marked = 1;
      reallymarkobject(g, gcvalue(gval(n)));
    }
  }
  /* 连接table到对应的列表 */
  if (g->gcstate == GCSpropagate) /* 广播阶段只会放入grayagain中 */
    linkgclist(h, g->grayagain);  /* 必须在atomic阶段重新遍历 */
  else if (hasww)  /* table有white->white条目? */
    linkgclist(h, g->ephemeron);  /* 必须重新广播 */
  else if (hasclears)  /* table有白色的key? */
    linkgclist(h, g->allweak);  /* 可能必须要清理白色key */
  else
    genlink(g, obj2gco(h));  /* 检测收集器是否仍然需要查看他 */
  return marked;
}


static void traversestrongtable (global_State *g, Table *h) {
  Node *n, *limit = gnodelast(h);
  unsigned int i;
  unsigned int asize = luaH_realasize(h);
  for (i = 0; i < asize; i++)  /* 遍历数组部分 */
    markvalue(g, &h->array[i]);
  for (n = gnode(h, 0); n < limit; n++) {  /* 遍历hash部分 */
    if (isempty(gval(n)))  /* 元素是空的? */
      clearkey(n);  /* 清理他的key */
    else {
      lua_assert(!keyisnil(n));
      /* 标记key-value */
      markkey(g, n);
      markvalue(g, gval(n));
    }
  }
  genlink(g, obj2gco(h));
}


static lu_mem traversetable (global_State *g, Table *h) {
  const char *weakkey, *weakvalue;
  const TValue *mode = gfasttm(g, h->metatable, TM_MODE);
  markobjectN(g, h->metatable);
  if (mode && ttisstring(mode) &&  /* 弱模式? */
      (cast_void(weakkey = strchr(svalue(mode), 'k')),
       cast_void(weakvalue = strchr(svalue(mode), 'v')),
       (weakkey || weakvalue))) {
    if (!weakkey)  /* 强key? */
      traverseweakvalue(g, h);
    else if (!weakvalue)  /* 强values? */
      traverseephemeron(g, h, 0);
    else  /* 弱kv */
      linkgclist(h, g->allweak);
  }
  else  /* 不是弱模式 */
    traversestrongtable(g, h);
  return 1 + h->alimit + 2 * allocsizenode(h);
}


static int traverseudata (global_State *g, Udata *u) {
  int i;
  markobjectN(g, u->metatable);  /* 标记元表 */
  for (i = 0; i < u->nuvalue; i++)
    markvalue(g, &u->uv[i].uv); // 标记user value
  genlink(g, obj2gco(u));
  return 1 + u->nuvalue;
}


/*
** 遍历函数原型. (当函数原型被构建，他的数组会比需要的大，这些额外的槽用NULL填充，所以使用‘markobjectN’)
*/
static int traverseproto (global_State *g, Proto *f) {
  int i;
  markobjectN(g, f->source);
  for (i = 0; i < f->sizek; i++)  /* 标记常量 */
    markvalue(g, &f->k[i]);
  for (i = 0; i < f->sizeupvalues; i++)  /* 标记upvalue名称 */
    markobjectN(g, f->upvalues[i].name);
  for (i = 0; i < f->sizep; i++)  /* 标记嵌入的方法 */
    markobjectN(g, f->p[i]);
  for (i = 0; i < f->sizelocvars; i++)  /* 标记本地变量名 */
    markobjectN(g, f->locvars[i].varname);
  return 1 + f->sizek + f->sizeupvalues + f->sizep + f->sizelocvars;
}


static int traverseCclosure (global_State *g, CClosure *cl) {
  int i;
  for (i = 0; i < cl->nupvalues; i++)  /* 标记他的upvalue */
    markvalue(g, &cl->upvalue[i]);
  return 1 + cl->nupvalues;
}

/*
** 遍历Lua闭包, 标记他的函数原型和他的upvalue
** (当闭包被创建时都为NULL)
*/
static int traverseLclosure (global_State *g, LClosure *cl) {
  int i;
  markobjectN(g, cl->p);  /* 标记他的函数原型 */
  for (i = 0; i < cl->nupvalues; i++) {  /* 查看他的upvalue */
    UpVal *uv = cl->upvals[i];
    markobjectN(g, uv);  /* 标记upvalue */
  }
  return 1 + cl->nupvalues;
}


/*
** 遍历一个线程，标记栈上的元素，并清除剩余的元素
** 保证整个栈上的元素是有效元素
** 线程没有屏障，在分代模式，老线程必须在每个周期都可访问，因为他们可能指向年轻对象
** 在增量模式中，线程在周期结束前仍然可能会被修改，因此必须在atomic阶段再次被访问
** 为了保证这种访问，如果线程不是新的，或者如果遍历是在传播阶段，那么他们必须在增量模式下被遍历
*/
static int traversethread (global_State *g, lua_State *th) {
  UpVal *uv;
  StkId o = th->stack.p;
  if (isold(th) || g->gcstate == GCSpropagate)
    linkgclist(th, g->grayagain);  /* 插入到‘grayagain’列表 */
  if (o == NULL)
    return 1;  /* 栈还没有完全构建 */
  lua_assert(g->gcstate == GCSatomic ||
             th->openupval == NULL || isintwups(th));
  for (; o < th->top.p; o++)  /* 标记栈中存活的元素 */
    markvalue(g, s2v(o));
  for (uv = th->openupval; uv != NULL; uv = uv->u.open.next)
    markobject(g, uv);  /* 打开的upvalue不能被收集 */
  if (g->gcstate == GCSatomic) {  /* 最后的遍历? */
    for (; o < th->stack_last.p + EXTRA_STACK; o++)
      setnilvalue(s2v(o));  /* 清空dead的栈片段 */
    /* 'remarkupvals'可能会把线程从‘twups’列表中移除 */
    if (!isintwups(th) && th->openupval != NULL) {
      th->twups = g->twups;  /* 链接回列表 */
      g->twups = th;
    }
  }
  else if (!g->gcemergency)
    luaD_shrinkstack(th); /* 紧急收集不需要改变堆栈  */
  return 1 + stacksize(th);
}


/*
** 遍历一个灰色对象，将其转换成黑色
*/
static lu_mem propagatemark (global_State *g) {
  GCObject *o = g->gray;
  nw2black(o);
  g->gray = *getgclist(o);  /* 从‘gray’列表中移除 */
  switch (o->tt) {
    case LUA_VTABLE: return traversetable(g, gco2t(o));
    case LUA_VUSERDATA: return traverseudata(g, gco2u(o));
    case LUA_VLCL: return traverseLclosure(g, gco2lcl(o));
    case LUA_VCCL: return traverseCclosure(g, gco2ccl(o));
    case LUA_VPROTO: return traverseproto(g, gco2p(o));
    case LUA_VTHREAD: return traversethread(g, gco2th(o));
    default: lua_assert(0); return 0;
  }
}


static lu_mem propagateall (global_State *g) {
  lu_mem tot = 0;
  while (g->gray)
    tot += propagatemark(g);
  return tot;
}


/*
** 遍历所有的蜉蝣表(ephemeron tables，也是弱key表)，将标记从key传播到value，重复直至收敛(没有新的标记)，‘die'表示反方向遍历，试图加快同一表中链的收敛速度
*/
static void convergeephemerons (global_State *g) {
  int changed;
  int dir = 0;
  do {
    GCObject *w;
    GCObject *next = g->ephemeron;
    g->ephemeron = NULL;  /* 遍历时table可能返回这个列表 */
    changed = 0;
    while ((w = next) != NULL) {  /* 遍历蜉蝣表 */
      Table *h = gco2t(w);
      next = h->gclist;  /* list将在循环中重新构建 */
      nw2black(h);  /* out of the list (for now) */
      if (traverseephemeron(g, h, dir)) {  /* 标记了一些值? */
        propagateall(g);  /* 广播变化 */
        changed = 1;  /* 将不得不重新访问所有的蜉蝣表 */
      }
    }
    dir = !dir;  /* 下次调整方向 */
  } while (changed);  /* 重复直至没有更多变化 */
}

/* }====================================================== */


/*
** {======================================================
** Sweep Functions
** =======================================================
*/


/*
** 清除’l'列表中所有弱表中没有被标记keys的项
*/
static void clearbykeys (global_State *g, GCObject *l) {
  for (; l; l = gco2t(l)->gclist) {
    Table *h = gco2t(l);
    Node *limit = gnodelast(h);
    Node *n;
    for (n = gnode(h, 0); n < limit; n++) {
      if (iscleared(g, gckeyN(n)))  /* 没有标记的key? */
        setempty(gval(n));  /* 移除项 */
      if (isempty(gval(n)))  /* 空项? */
        clearkey(n);  /* 清除他的key */
    }
  }
}


/*
** 清除’l'列表中所有弱表中没有被标记values的项直至’f'元素
*/
static void clearbyvalues (global_State *g, GCObject *l, GCObject *f) {
  for (; l != f; l = gco2t(l)->gclist) {
    Table *h = gco2t(l);
    Node *n, *limit = gnodelast(h);
    unsigned int i;
    unsigned int asize = luaH_realasize(h);
    for (i = 0; i < asize; i++) {
      TValue *o = &h->array[i];
      if (iscleared(g, gcvalueN(o)))  /* value被收集了? */
        setempty(o);  /* 移除项 */
    }
    for (n = gnode(h, 0); n < limit; n++) {
      if (iscleared(g, gcvalueN(gval(n))))  /* 没有标记value? */
        setempty(gval(n));  /* 移除项 */
      if (isempty(gval(n)))  /* 项是空的? */
        clearkey(n);  /* 移除key */
    }
  }
}


static void freeupval (lua_State *L, UpVal *uv) {
  if (upisopen(uv))
    luaF_unlinkupval(uv);
  luaM_free(L, uv);
}


static void freeobj (lua_State *L, GCObject *o) {
  switch (o->tt) {
    case LUA_VPROTO:
      luaF_freeproto(L, gco2p(o));
      break;
    case LUA_VUPVAL:
      freeupval(L, gco2upv(o));
      break;
    case LUA_VLCL: {
      LClosure *cl = gco2lcl(o);
      luaM_freemem(L, cl, sizeLclosure(cl->nupvalues));
      break;
    }
    case LUA_VCCL: {
      CClosure *cl = gco2ccl(o);
      luaM_freemem(L, cl, sizeCclosure(cl->nupvalues));
      break;
    }
    case LUA_VTABLE:
      luaH_free(L, gco2t(o));
      break;
    case LUA_VTHREAD:
      luaE_freethread(L, gco2th(o));
      break;
    case LUA_VUSERDATA: {
      Udata *u = gco2u(o);
      luaM_freemem(L, o, sizeudata(u->nuvalue, u->len));
      break;
    }
    case LUA_VSHRSTR: {
      TString *ts = gco2ts(o);
      luaS_remove(L, ts);
      luaM_freemem(L, ts, sizelstring(ts->shrlen));
      break;
    }
    case LUA_VLNGSTR: {
      TString *ts = gco2ts(o);
      luaM_freemem(L, ts, sizelstring(ts->u.lnglen));
      break;
    }
    default: lua_assert(0);
  }
}


/*
** 从删除的死对象列表中清除最多'countin'个元素，其中死对象是指一个标记为老(非当前)白的对象
** 修改所有的非死对象颜色为白色(当前白)为下一论GC做准备。返回继续遍历的位置，如果遍历结束则返回NULL('*countout'给出了遍历过的元素个数)
*/
static GCObject **sweeplist (lua_State *L, GCObject **p, int countin,
                             int *countout) {
  global_State *g = G(L);
  int ow = otherwhite(g);
  int i;
  int white = luaC_white(g);  /* 当前白 */
  for (i = 0; *p != NULL && i < countin; i++) {
    GCObject *curr = *p;
    int marked = curr->marked;
    if (isdeadm(ow, marked)) {  /* 'curr'已经死了? */
      *p = curr->next;  /* 从列表中移除’curr' */
      freeobj(L, curr);  /* 释放‘curr' */
    }
    else {  /* 修改标记为白色 */
      curr->marked = cast_byte((marked & ~maskgcbits) | white);
      p = &curr->next;  /* 下一个元素 */
    }
  }
  if (countout)
    *countout = i;  /* 遍历过的元素个数 */
  return (*p == NULL) ? NULL : p;
}


/*
** 清除列表直至一个活动对象(或列表结束)
*/
static GCObject **sweeptolive (lua_State *L, GCObject **p) {
  GCObject **old = p;
  do {
    p = sweeplist(L, p, 1, NULL);
  } while (p == old);
  return p;
}

/* }====================================================== */


/*
** {======================================================
** 终结(析构)
** =======================================================
*/

/*
** 如果可能，缩小字符串表
*/
static void checkSizes (lua_State *L, global_State *g) {
  if (!g->gcemergency) {
    if (g->strt.nuse < g->strt.size / 4) {  /* string table太大了? */
      l_mem olddebt = g->GCdebt;
      luaS_resize(L, g->strt.size / 2);
      g->GCestimate += g->GCdebt - olddebt;  /* 正确的estimate */
    }
  }
}


/*
** 从'tobefnz'列表中获取下一个udata以终结,并且将其重新连接如’allgc'列表
*/
static GCObject *udata2finalize (global_State *g) {
  GCObject *o = g->tobefnz;  /* 获取第一个元素 */
  lua_assert(tofinalize(o));
  g->tobefnz = o->next;  /* 将其从‘tobefnz'列表中移除 */
  o->next = g->allgc;  /* 重新连接如’allgc'列表 */
  g->allgc = o;
  resetbit(o->marked, FINALIZEDBIT);  /* 对象再次变成”正常“状态 */
  if (issweepphase(g))
    makewhite(g, o);  /* "清除"对象 */
  else if (getage(o) == G_OLD1)
    g->firstold1 = o;  /* 列表中的第一个OLD1对象 */
  return o;
}


static void dothecall (lua_State *L, void *ud) {
  UNUSED(ud);
  luaD_callnoyield(L, L->top.p - 2, 0);
}


static void GCTM (lua_State *L) {
  global_State *g = G(L);
  const TValue *tm;
  TValue v;
  lua_assert(!g->gcemergency);
  setgcovalue(L, &v, udata2finalize(g));
  tm = luaT_gettmbyobj(L, &v, TM_GC);
  if (!notm(tm)) {  /* 这有一个终结器? */
    int status;
    lu_byte oldah = L->allowhook;
    int oldgcstp  = g->gcstp;
    g->gcstp |= GCSTPGC;  /* 避免GC步骤 */
    L->allowhook = 0;  /* 整个GC元方法中停止hook */
    setobj2s(L, L->top.p++, tm);  /* 压入终结器... */
    setobj2s(L, L->top.p++, &v);  /* 压入他的参数 */
    L->ci->callstatus |= CIST_FIN;
    status = luaD_pcall(L, dothecall, NULL, savestack(L, L->top.p - 2), 0);
    L->ci->callstatus &= ~CIST_FIN;  /* 不再运行终结器 */
    L->allowhook = oldah;  /* 恢复hook */
    g->gcstp = oldgcstp;  /* 恢复状态 */
    if (l_unlikely(status != LUA_OK)) {  /* 运行__gc有错误? */
      luaE_warnerror(L, "__gc");
      L->top.p--;  /* 弹出错误对象 */
    }
  }
}


/*
** 调用一些终结器
*/
static int runafewfinalizers (lua_State *L, int n) {
  global_State *g = G(L);
  int i;
  for (i = 0; i < n && g->tobefnz; i++)
    GCTM(L);  /* 调用一个终结器 */
  return i;
}


/*
** 调用所有挂起的终结器
*/
static void callallpendingfinalizers (lua_State *L) {
  global_State *g = G(L);
  while (g->tobefnz)
    GCTM(L);
}


/*
** 查找’p'列表的最后一个‘next'字段，用于在其末尾添加元素
*/
static GCObject **findlast (GCObject **p) {
  while (*p != NULL)
    p = &(*p)->next;
  return p;
}


/*
** 移动所有不可达(或’all'对象)从'finobj'列表到'tobefnz'列表(用于终结)
** (注意’findobjold1'后的对象不能是白色，所以他们不需要被遍历。在增量模式中，'findobjold1'是NULL，所以整个列表都会被遍历
*/
static void separatetobefnz (global_State *g, int all) {
  GCObject *curr;
  GCObject **p = &g->finobj;
  GCObject **lastnext = findlast(&g->tobefnz);
  while ((curr = *p) != g->finobjold1) {  /* 遍历所有可终结对象 */
    lua_assert(tofinalize(curr));
    if (!(iswhite(curr) || all))  /* 没有被收集? */
      p = &curr->next;
    else {
      if (curr == g->finobjsur)  /* removing 'finobjsur'? */
        g->finobjsur = curr->next;  /* correct it */
      *p = curr->next;  /* 从‘findobj'列表中移除 */
      curr->next = *lastnext;  /* 连接到'tobefnz'列表的末尾 */
      *lastnext = curr;
      lastnext = &curr->next;
    }
  }
}


/*
** 如果指针’p‘指向’o‘，将他移动到下一个元素
*/
static void checkpointer (GCObject **p, GCObject *o) {
  if (o == *p)
    *p = o->next;
}


/*
** 矫正'allgc'列表中对象的指针
** 对象’o'被从列表中移除时调用
*/
static void correctpointers (global_State *g, GCObject *o) {
  checkpointer(&g->survival, o);
  checkpointer(&g->old1, o);
  checkpointer(&g->reallyold, o);
  checkpointer(&g->firstold1, o);
}


/*
** 如果对象’o‘有终结器，将他从’allgc'列表中移除(必须搜索这个列表以找到他)并且连接到‘finobj'列表
*/
void luaC_checkfinalizer (lua_State *L, GCObject *o, Table *mt) {
  global_State *g = G(L);
  if (tofinalize(o) ||                 /* 对象已经被标记... */
      gfasttm(g, mt, TM_GC) == NULL ||    /* 或者没有终结器... */
      (g->gcstp & GCSTPCLS))                   /* 或者正在关闭luaState? */
    return;
  else {  /* 移动'o'到'finobj'列表 */
    GCObject **p;
    if (issweepphase(g)) {
      makewhite(g, o);  /* "清除"对象'o' */
      if (g->sweepgc == &o->next)  /* 不应该移除'sweepgc'对象 */
        g->sweepgc = sweeptolive(L, g->sweepgc);  /* 改变'sweepgc' */
    }
    else
      correctpointers(g, o);
    /* 查找指向’o'的指针，并将其移除 */
    for (p = &g->allgc; *p != o; p = &(*p)->next) { /* empty */ }
    *p = o->next;  /* 从'allgc'列表中移除 */
    o->next = g->finobj;  /* 连接到'finobj'列表的末尾 */
    g->finobj = o;
    l_setbit(o->marked, FINALIZEDBIT);  /* 标记‘o' */
  }
}

/* }====================================================== */


/*
** {======================================================
** 分代收集
** =======================================================
*/


/*
** 设置等待下一轮GC周期的”时间”；周期将在内存达到阈值('estimate' * pause / PAUSEADJ)时开始
** 因为Lua不能通过小于PAUSEADJ字节开启
*/
static void setpause (global_State *g) {
  l_mem threshold, debt;
  int pause = getgcparam(g->gcpause);
  l_mem estimate = g->GCestimate / PAUSEADJ;  /* 调整'estimate' */
  lua_assert(estimate > 0);
  threshold = (pause < MAX_LMEM / estimate)  /* 溢出(estimate * pause < MAX_LMEM)? */
            ? estimate * pause  /* 没有溢出 */
            : MAX_LMEM;  /* 溢出; 截断至最大值 */
  debt = gettotalbytes(g) - threshold;
  if (debt > 0) debt = 0;
  luaE_setdebt(g, debt);
}


/*
** Sweep a list of objects to enter generational mode.  Deletes dead
** objects and turns the non dead to old. All non-dead threads---which
** are now old---must be in a gray list. Everything else is not in a
** gray list. Open upvalues are also kept gray.
*/
static void sweep2old (lua_State *L, GCObject **p) {
  GCObject *curr;
  global_State *g = G(L);
  while ((curr = *p) != NULL) {
    if (iswhite(curr)) {  /* is 'curr' dead? */
      lua_assert(isdead(g, curr));
      *p = curr->next;  /* remove 'curr' from list */
      freeobj(L, curr);  /* erase 'curr' */
    }
    else {  /* all surviving objects become old */
      setage(curr, G_OLD);
      if (curr->tt == LUA_VTHREAD) {  /* threads must be watched */
        lua_State *th = gco2th(curr);
        linkgclist(th, g->grayagain);  /* insert into 'grayagain' list */
      }
      else if (curr->tt == LUA_VUPVAL && upisopen(gco2upv(curr)))
        set2gray(curr);  /* open upvalues are always gray */
      else  /* everything else is black */
        nw2black(curr);
      p = &curr->next;  /* go to next element */
    }
  }
}


/*
** 分代模式的清除。删除死亡对象. (因为收集不是增量模式，清除阶段没有“新白”对象。因此所有白色对象都必须死。)
** 对于没有死亡的对象，将他们的年龄往前推进并且清除新对象的颜色。(老对象保留他们的颜色)
** G_TOUCHED1和G_TOUCHED2年龄的对象不能再这里推进，因为老一辈的对象通常不在这里清除。他们将被列入到‘correctgraylist'
** 这个函数也会从所有灰色列表中移除白色对象
*/
static GCObject **sweepgen (lua_State *L, global_State *g, GCObject **p,
                            GCObject *limit, GCObject **pfirstold1) {
  static const lu_byte nextage[] = {
    G_SURVIVAL,  /* from G_NEW */
    G_OLD1,      /* from G_SURVIVAL */
    G_OLD1,      /* from G_OLD0 */
    G_OLD,       /* from G_OLD1 */
    G_OLD,       /* from G_OLD (do not change) */
    G_TOUCHED1,  /* from G_TOUCHED1 (do not change) */
    G_TOUCHED2   /* from G_TOUCHED2 (do not change) */
  };
  int white = luaC_white(g);
  GCObject *curr;
  while ((curr = *p) != limit) {
    if (iswhite(curr)) {  /* is 'curr' dead? */
      lua_assert(!isold(curr) && isdead(g, curr));
      *p = curr->next;  /* remove 'curr' from list */
      freeobj(L, curr);  /* erase 'curr' */
    }
    else {  /* correct mark and age */
      if (getage(curr) == G_NEW) {  /* new objects go back to white */
        int marked = curr->marked & ~maskgcbits;  /* erase GC bits */
        curr->marked = cast_byte(marked | G_SURVIVAL | white);
      }
      else {  /* all other objects will be old, and so keep their color */
        setage(curr, nextage[getage(curr)]);
        if (getage(curr) == G_OLD1 && *pfirstold1 == NULL)
          *pfirstold1 = curr;  /* first OLD1 object in the list */
      }
      p = &curr->next;  /* go to next element */
    }
  }
  return p;
}


/*
** 遍历列表使其中所有元素变成白色并且清空他们的年龄,在增量模式中，所有对象都是新的，除了固定字符串(总是旧的)
*/
static void whitelist (global_State *g, GCObject *p) {
  int white = luaC_white(g);
  for (; p != NULL; p = p->next)
    p->marked = cast_byte((p->marked & ~maskgcbits) | white);
}


/*
** Correct a list of gray objects. Return pointer to where rest of the
** list should be linked.
** Because this correction is done after sweeping, young objects might
** be turned white and still be in the list. They are only removed.
** 'TOUCHED1' objects are advanced to 'TOUCHED2' and remain on the list;
** Non-white threads also remain on the list; 'TOUCHED2' objects become
** regular old; they and anything else are removed from the list.
*/
static GCObject **correctgraylist (GCObject **p) {
  GCObject *curr;
  while ((curr = *p) != NULL) {
    GCObject **next = getgclist(curr);
    if (iswhite(curr))
      goto remove;  /* remove all white objects */
    else if (getage(curr) == G_TOUCHED1) {  /* touched in this cycle? */
      lua_assert(isgray(curr));
      nw2black(curr);  /* make it black, for next barrier */
      changeage(curr, G_TOUCHED1, G_TOUCHED2);
      goto remain;  /* keep it in the list and go to next element */
    }
    else if (curr->tt == LUA_VTHREAD) {
      lua_assert(isgray(curr));
      goto remain;  /* keep non-white threads on the list */
    }
    else {  /* everything else is removed */
      lua_assert(isold(curr));  /* young objects should be white here */
      if (getage(curr) == G_TOUCHED2)  /* advance from TOUCHED2... */
        changeage(curr, G_TOUCHED2, G_OLD);  /* ... to OLD */
      nw2black(curr);  /* make object black (to be removed) */
      goto remove;
    }
    remove: *p = *next; continue;
    remain: p = next; continue;
  }
  return p;
}


/*
** Correct all gray lists, coalescing them into 'grayagain'.
*/
static void correctgraylists (global_State *g) {
  GCObject **list = correctgraylist(&g->grayagain);
  *list = g->weak; g->weak = NULL;
  list = correctgraylist(list);
  *list = g->allweak; g->allweak = NULL;
  list = correctgraylist(list);
  *list = g->ephemeron; g->ephemeron = NULL;
  correctgraylist(list);
}


/*
** Mark black 'OLD1' objects when starting a new young collection.
** Gray objects are already in some gray list, and so will be visited
** in the atomic step.
*/
static void markold (global_State *g, GCObject *from, GCObject *to) {
  GCObject *p;
  for (p = from; p != to; p = p->next) {
    if (getage(p) == G_OLD1) {
      lua_assert(!iswhite(p));
      changeage(p, G_OLD1, G_OLD);  /* now they are old */
      if (isblack(p))
        reallymarkobject(g, p);
    }
  }
}


/*
** Finish a young-generation collection.
*/
static void finishgencycle (lua_State *L, global_State *g) {
  correctgraylists(g);
  checkSizes(L, g);
  g->gcstate = GCSpropagate;  /* skip restart */
  if (!g->gcemergency)
    callallpendingfinalizers(L);
}


/*
** Does a young collection. First, mark 'OLD1' objects. Then does the
** atomic step. Then, sweep all lists and advance pointers. Finally,
** finish the collection.
*/
static void youngcollection (lua_State *L, global_State *g) {
  GCObject **psurvival;  /* to point to first non-dead survival object */
  GCObject *dummy;  /* dummy out parameter to 'sweepgen' */
  lua_assert(g->gcstate == GCSpropagate);
  if (g->firstold1) {  /* are there regular OLD1 objects? */
    markold(g, g->firstold1, g->reallyold);  /* mark them */
    g->firstold1 = NULL;  /* no more OLD1 objects (for now) */
  }
  markold(g, g->finobj, g->finobjrold);
  markold(g, g->tobefnz, NULL);
  atomic(L);

  /* sweep nursery and get a pointer to its last live element */
  g->gcstate = GCSswpallgc;
  psurvival = sweepgen(L, g, &g->allgc, g->survival, &g->firstold1);
  /* sweep 'survival' */
  sweepgen(L, g, psurvival, g->old1, &g->firstold1);
  g->reallyold = g->old1;
  g->old1 = *psurvival;  /* 'survival' survivals are old now */
  g->survival = g->allgc;  /* all news are survivals */

  /* repeat for 'finobj' lists */
  dummy = NULL;  /* no 'firstold1' optimization for 'finobj' lists */
  psurvival = sweepgen(L, g, &g->finobj, g->finobjsur, &dummy);
  /* sweep 'survival' */
  sweepgen(L, g, psurvival, g->finobjold1, &dummy);
  g->finobjrold = g->finobjold1;
  g->finobjold1 = *psurvival;  /* 'survival' survivals are old now */
  g->finobjsur = g->finobj;  /* all news are survivals */

  sweepgen(L, g, &g->tobefnz, NULL, &dummy);
  finishgencycle(L, g);
}


/*
** Clears all gray lists, sweeps objects, and prepare sublists to enter
** generational mode. The sweeps remove dead objects and turn all
** surviving objects to old. Threads go back to 'grayagain'; everything
** else is turned black (not in any gray list).
*/
static void atomic2gen (lua_State *L, global_State *g) {
  cleargraylists(g);
  /* sweep all elements making them old */
  g->gcstate = GCSswpallgc;
  sweep2old(L, &g->allgc);
  /* everything alive now is old */
  g->reallyold = g->old1 = g->survival = g->allgc;
  g->firstold1 = NULL;  /* there are no OLD1 objects anywhere */

  /* repeat for 'finobj' lists */
  sweep2old(L, &g->finobj);
  g->finobjrold = g->finobjold1 = g->finobjsur = g->finobj;

  sweep2old(L, &g->tobefnz);

  g->gckind = KGC_GEN;
  g->lastatomic = 0;
  g->GCestimate = gettotalbytes(g);  /* base for memory control */
  finishgencycle(L, g);
}


/*
** Set debt for the next minor collection, which will happen when memory grows 'genminormul'%.
*/
static void setminordebt (global_State *g) {
  luaE_setdebt(g, -(cast(l_mem, (gettotalbytes(g) / 100)) * g->genminormul));
}


/*
** 进入分代模式. Must go until the end of an atomic cycle
** to ensure that all objects are correctly marked and weak tables
** are cleared. Then, turn all objects into old and finishes the
** collection.
*/
static lu_mem entergen (lua_State *L, global_State *g) {
  lu_mem numobjs;
  luaC_runtilstate(L, bitmask(GCSpause));  /* 准备开始新周期 */
  luaC_runtilstate(L, bitmask(GCSpropagate));  /* 开始新的周期 */
  numobjs = atomic(L);  /* 传播所有内容然后做一次原子处理 */
  atomic2gen(L, g);
  setminordebt(g);  /* set debt assuming next cycle will be minor */
  return numobjs;
}


/*
** 进入增量模式. 将所有对象转为白色，使中间表指向NULL(以避免无效指针)，然后进入暂停状态
*/
static void enterinc (global_State *g) {
  whitelist(g, g->allgc);
  g->reallyold = g->old1 = g->survival = NULL;
  whitelist(g, g->finobj);
  whitelist(g, g->tobefnz);
  g->finobjrold = g->finobjold1 = g->finobjsur = NULL;
  g->gcstate = GCSpause;
  g->gckind = KGC_INC;
  g->lastatomic = 0;
}


/*
** 修改收集模式
*/
void luaC_changemode (lua_State *L, int newmode) {
  global_State *g = G(L);
  if (newmode != g->gckind) {
    if (newmode == KGC_GEN)
      entergen(L, g);
    else
      enterinc(g);
  }
  g->lastatomic = 0;
}


/*
** 在分代模式中做一次完整的收集
*/
static lu_mem fullgen (lua_State *L, global_State *g) {
  enterinc(g);
  return entergen(L, g);
}


/*
** Does a major collection after last collection was a "bad collection".
**
** When the program is building a big structure, it allocates lots of
** memory but generates very little garbage. In those scenarios,
** the generational mode just wastes time doing small collections, and
** major collections are frequently what we call a "bad collection", a
** collection that frees too few objects. To avoid the cost of switching
** between generational mode and the incremental mode needed for full
** (major) collections, the collector tries to stay in incremental mode
** after a bad collection, and to switch back to generational mode only
** after a "good" collection (one that traverses less than 9/8 objects
** of the previous one).
** The collector must choose whether to stay in incremental mode or to
** switch back to generational mode before sweeping. At this point, it
** does not know the real memory in use, so it cannot use memory to
** decide whether to return to generational mode. Instead, it uses the
** number of objects traversed (returned by 'atomic') as a proxy. The
** field 'g->lastatomic' keeps this count from the last collection.
** ('g->lastatomic != 0' also means that the last collection was bad.)
*/
static void stepgenfull (lua_State *L, global_State *g) {
  lu_mem newatomic;  /* count of traversed objects */
  lu_mem lastatomic = g->lastatomic;  /* count from last collection */
  if (g->gckind == KGC_GEN)  /* still in generational mode? */
    enterinc(g);  /* enter incremental mode */
  luaC_runtilstate(L, bitmask(GCSpropagate));  /* start new cycle */
  newatomic = atomic(L);  /* mark everybody */
  if (newatomic < lastatomic + (lastatomic >> 3)) {  /* good collection? */
    atomic2gen(L, g);  /* return to generational mode */
    setminordebt(g);
  }
  else {  /* another bad collection; stay in incremental mode */
    g->GCestimate = gettotalbytes(g);  /* first estimate */;
    entersweep(L);
    luaC_runtilstate(L, bitmask(GCSpause));  /* finish collection */
    setpause(g);
    g->lastatomic = newatomic;
  }
}


/*
** 做一个分代“步骤”
** Usually, this means doing a minor collection and setting the debt to make another collection when memory grows 'genminormul'% larger.
** However, there are exceptions.  If memory grows 'genmajormul'%
** larger than it was at the end of the last major collection (kept
** in 'g->GCestimate'), the function does a major collection. At the
** end, it checks whether the major collection was able to free a
** decent amount of memory (at least half the growth in memory since
** previous major collection). If so, the collector keeps its state,
** and the next collection will probably be minor again. Otherwise,
** we have what we call a "bad collection". In that case, set the field
** 'g->lastatomic' to signal that fact, so that the next collection will
** go to 'stepgenfull'.
**
** 'GCdebt <= 0' means an explicit call to GC step with "size" zero;
** in that case, do a minor collection.
*/
static void genstep (lua_State *L, global_State *g) {
  if (g->lastatomic != 0)  /* last collection was a bad one? */
    stepgenfull(L, g);  /* 做一次完整的步骤 */
  else {
    lu_mem majorbase = g->GCestimate;  /* memory after last major collection */
    lu_mem majorinc = (majorbase / 100) * getgcparam(g->genmajormul);
    if (g->GCdebt > 0 && gettotalbytes(g) > majorbase + majorinc) {
      lu_mem numobjs = fullgen(L, g);  /* do a major collection */
      if (gettotalbytes(g) < majorbase + (majorinc / 2)) {
        /* collected at least half of memory growth since last major
           collection; keep doing minor collections. */
        lua_assert(g->lastatomic == 0);
      }
      else {  /* bad collection */
        g->lastatomic = numobjs;  /* signal that last collection was bad */
        setpause(g);  /* do a long wait for next (major) collection */
      }
    }
    else {  /* regular case; do a minor collection */
      youngcollection(L, g);
      setminordebt(g);
      g->GCestimate = majorbase;  /* preserve base value */
    }
  }
  lua_assert(isdecGCmodegen(g));
}

/* }====================================================== */


/*
** {======================================================
** GC控制
** =======================================================
*/


/*
** 进入清除阶段
** 对'sweeptolive'的调用使指针指向列表中的对象(而不是头)，因此真正的清除不需要跳过在”now“和真正清扫之间创建的对象
*/
static void entersweep (lua_State *L) {
  global_State *g = G(L);
  g->gcstate = GCSswpallgc;
  lua_assert(g->sweepgc == NULL);
  g->sweepgc = sweeptolive(L, &g->allgc);
}


/*
** 删除所有在‘p'列表中的对象直至’limit'对象(不包括)
*/
static void deletelist (lua_State *L, GCObject *p, GCObject *limit) {
  while (p != limit) {
    GCObject *next = p->next;
    freeobj(L, p);
    p = next;
  }
}


/*
** 在给定的Lua状态下调用对象的所有终结器，然后释放除主线程之外的所有对象。
*/
void luaC_freeallobjects (lua_State *L) {
  global_State *g = G(L);
  g->gcstp = GCSTPCLS;  /* 这之后没有额外的终结器 */
  luaC_changemode(L, KGC_INC);
  separatetobefnz(g, 1);  /* 分隔所有有终结器的对象 */
  lua_assert(g->finobj == NULL);
  callallpendingfinalizers(L);
  deletelist(L, g->allgc, obj2gco(g->mainthread));
  lua_assert(g->finobj == NULL);  /* 没有新的终结器 */
  deletelist(L, g->fixedgc, NULL);  /* 释放常驻内存的对象 */
  lua_assert(g->strt.nuse == 0);
}


static lu_mem atomic (lua_State *L) {
  global_State *g = G(L);
  lu_mem work = 0;
  GCObject *origweak, *origall;
  GCObject *grayagain = g->grayagain;  /* 保存原来的列表 */
  g->grayagain = NULL;
  lua_assert(g->ephemeron == NULL && g->weak == NULL);
  lua_assert(!iswhite(g->mainthread));
  g->gcstate = GCSatomic;
  markobject(g, L);  /* 标记运行中的线程 */
  /* 注册表和全局元表可能被API修改 */
  markvalue(g, &g->l_registry);
  markmt(g);
  work += propagateall(g);  /* 清空‘gray’列表 */
  /* 标记(可能)已死亡的线程的upvalue */
  work += remarkupvals(g);
  work += propagateall(g);  /* 广播变化 */
  g->gray = grayagain;
  work += propagateall(g);  /* 遍历'grayagain'列表 */
  convergeephemerons(g);
  /* 到这里，所有的强引用对象都被标记了 */
  /* 在检查终结器前，清空弱表中的值 */
  clearbyvalues(g, g->weak, NULL);
  clearbyvalues(g, g->allweak, NULL);
  origweak = g->weak; origall = g->allweak;
  separatetobefnz(g, 0);  /* 把要被终结的对象分离出来 */
  work += markbeingfnz(g);  /* 标记需要终结器的对象 */
  work += propagateall(g);  /* 标记，广播“复活” */
  convergeephemerons(g);
  /* 到这时，所有复活的对象都被标记了 */
  /* 从弱表中移除死亡的对象 */
  clearbykeys(g, g->ephemeron);  /* 清除所有ephemeron表中的键 */
  clearbykeys(g, g->allweak);  /* 清除所有'allweak'表中的键 */
  /* 从复活的弱表中清除值 */
  clearbyvalues(g, g->weak, origweak);
  clearbyvalues(g, g->allweak, origall);
  luaS_clearcache(g);
  g->currentwhite = cast_byte(otherwhite(g));  /* 翻转当前白色 */
  lua_assert(g->gray == NULL);
  return work;  /* 被’atomic‘标记的对象数 */
}


static int sweepstep (lua_State *L, global_State *g,
                      int nextstate, GCObject **nextlist) {
  if (g->sweepgc) {
    l_mem olddebt = g->GCdebt;
    int count;
    g->sweepgc = sweeplist(L, g->sweepgc, GCSWEEPMAX, &count);
    g->GCestimate += g->GCdebt - olddebt;  /* 更新estimate */
    return count;
  }
  else {  /* 进入下一个状态 */
    g->gcstate = nextstate;
    g->sweepgc = nextlist;
    return 0;
  }
}


static lu_mem singlestep (lua_State *L) {
  global_State *g = G(L);
  lu_mem work;
  lua_assert(!g->gcstopem);  /* 收集器不可重入 */
  g->gcstopem = 1;  /* 收集时不能运行紧急收集 */
  switch (g->gcstate) {
    case GCSpause: {
      restartcollection(g); // 重启收集
      g->gcstate = GCSpropagate;  // 进入传播阶段
      work = 1;
      break;
    }
    case GCSpropagate: {
      if (g->gray == NULL) {  /* 没有更多的灰色对象? */
        g->gcstate = GCSenteratomic;  /* 完成传播阶段 */
        work = 0;
      }
      else
        work = propagatemark(g);  /* 遍历一个灰色对象 */
      break;
    }
    case GCSenteratomic: {
      work = atomic(L);
      entersweep(L);
      g->GCestimate = gettotalbytes(g);  /* 第一次预估 */;
      break;
    }
    case GCSswpallgc: {  /* 清除普通对象 */
      work = sweepstep(L, g, GCSswpfinobj, &g->finobj);
      break;
    }
    case GCSswpfinobj: {  /* 清除有终结器的对象 */
      work = sweepstep(L, g, GCSswptobefnz, &g->tobefnz);
      break;
    }
    case GCSswptobefnz: {  /* 清除尚未执行终结器的对象 */
      work = sweepstep(L, g, GCSswpend, NULL);
      break;
    }
    case GCSswpend: {  /* 结束清除 */
      checkSizes(L, g);
      g->gcstate = GCScallfin;
      work = 0;
      break;
    }
    case GCScallfin: {  /* 调用终结器 */
      if (g->tobefnz && !g->gcemergency) {
        g->gcstopem = 0;  /* 在终结器执行期间允许正常收集 */
        work = runafewfinalizers(L, GCFINMAX) * GCFINALIZECOST;
      }
      else {  /* 紧急模式或没有更多终结器 */
        g->gcstate = GCSpause;  /* 完成收集 */
        work = 0;
      }
      break;
    }
    default: lua_assert(0); return 0;
  }
  g->gcstopem = 0;
  return work;
}


/*
** 推进垃圾收集器，直到它达到“statemask”允许的状态
*/
void luaC_runtilstate (lua_State *L, int statesmask) {
  global_State *g = G(L);
  while (!testbit(statesmask, g->gcstate))
    singlestep(L);
}



/*
** 执行一个基础的增量步骤. debt和step size(步骤尺寸)从字节转换成“units of work(工作单位)”
** “工作单元” = g->GCdebt / WORK2MEM
** 然后这个函数循环调用单个步骤直到添加那么多工作单位或完成一个GC周期(暂停状态)
** 最后，他设置debt以控制下个步骤什么时候执行
*/
static void incstep (lua_State *L, global_State *g) {
  int stepmul = (getgcparam(g->gcstepmul) | 1);  /* 避免除以0 */
  l_mem debt = (g->GCdebt / WORK2MEM) * stepmul;  // 当前债务需要完成的work数(此时g->GCdebt >= 0)
  l_mem stepsize = (g->gcstepsize <= log2maxs(l_mem))
                 ? ((cast(l_mem, 1) << g->gcstepsize) / WORK2MEM) * stepmul
                 : MAX_LMEM;  /* 溢出，保持最大值 */
  do {  /* 循环直至暂停或有足够的“信用”(负的debt) */
    lu_mem work = singlestep(L);  /* 执行一个单独的步骤 */
    debt -= work;
  } while (debt > -stepsize && g->gcstate != GCSpause); /* 债务少于步长或者gc状态暂停 */
  if (g->gcstate == GCSpause)
    setpause(g);  /* 暂停直至下一个周期 */
  else {
    debt = (debt / stepmul) * WORK2MEM;  /* 转换“工作单元”为字节 */
    luaE_setdebt(g, debt);
  }
}

/*
** 如果收集器正在运行，执行一个基础GC步骤（如果收集器没在运行中，设置一个合理的debt以避免每次check他都被调用)
*/
void luaC_step (lua_State *L) {
  global_State *g = G(L);
  if (!gcrunning(g))  /* 没有运行? */ {
    luaE_setdebt(g, -2000);
  }
  else {
    if(isdecGCmodegen(g))
      genstep(L, g);
    else
      incstep(L, g);
  }
}


/*
** 通过增量模式执行一次完整的垃圾收集，在收集前，检测'keepinvariant'，如果是true，可能有一些对象被标记成了黑色，因此收集器必须清除所有对象以将其变回白色(因为白色没有改变，因此不会收集任何东西)。
*/
static void fullinc (lua_State *L, global_State *g) {
  if (keepinvariant(g))
    entersweep(L); /* 将所有对象标记为白色(清除颜色标记) */
  /* 完成所有挂起的清理阶段以开启一个新的周期 */
  luaC_runtilstate(L, bitmask(GCSpause));
  luaC_runtilstate(L, bitmask(GCScallfin));
  /* 一次完成GC周期后estimate必须正确 */
  lua_assert(g->GCestimate == gettotalbytes(g));
  luaC_runtilstate(L, bitmask(GCSpause));  /* 完成收集 */
  setpause(g);
}


/*
** 执行一次完整的GC周期，如果'isemergency',设置一个标志来避免一些可能以意想不到的方式改变解释器状态的操作(运行终结器和收缩一些结构)
*/
void luaC_fullgc (lua_State *L, int isemergency) {
  global_State *g = G(L);
  lua_assert(!g->gcemergency);
  g->gcemergency = isemergency;
  if (g->gckind == KGC_INC)
    fullinc(L, g);
  else
    fullgen(L, g);
  g->gcemergency = 0;
}

/* }====================================================== */


